
//220.存在重复元素III
class Solution {
    #define LL long long
    LL size;   //用于计算当前数据放在哪一个桶里面
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int indexDiff, int valueDiff) {
        //使用哈希桶进行处理
        size=valueDiff+1L;  //1L指的是将1转化为long long类型

        unordered_map<LL,LL> m; //作为存储数据的哈希桶
        int left=0,n=nums.size();
        for(int right=0;right<n;right++)
        {
            LL val=nums[right];
            LL index=getIdx(val);  //记录放在哪一个桶中

            if(m.count(index)) return true;

            LL l=index-1,r=index+1;  //判断左右两个桶中的数据是否满足条件
            if((m.count(l)&&abs(val-m[l])<=valueDiff)||(m.count(r)&&abs(val-m[r])<=valueDiff)) return true;

            if(right-left>=indexDiff)
                m.erase(getIdx(nums[left++]));
            
            m.insert({index,val});
        }
        return false;
    }

    LL getIdx(LL u)
    {
        return u>=0?u/size:(u+1)/size-1;
    } 
};